#include <iostream>
#include <queue>

using namespace std;

// 结点
typedef struct node
{
    int value;
    int toNode;
    int visited;
    struct node* next;
}Node;

// 邻接表
typedef struct neigborNode
{
    Node* fNode;
    int length;
}neigborNode;

// 边
typedef struct edge
{
    int from;
    int to;
    int value;
}edge;

class Graph
{
    public:
        Graph(int n) // n为结点数
        {
            neigborList=new neigborNode[n];
            for(int i=0;i<n;i++)
            {
                neigborList[i].fNode=NULL;
                neigborList[i].length=0;
            }
            length=n;
        }

        void createNode(edge[],int);
        void insertNode(edge);

        //
        void showGraph();

        void setVisited(Node*,int);
        void clearVisited();

        // 广度优先搜索
        void BFS(int);

        // 深度优先搜索
        void DFS(int,int[]);


        int getLength()
        {
            return this->length;
        }
    private:
        neigborNode *neigborList;
        int length;
};

// 
void Graph::showGraph()
{
    for(int i=0;i<this->length;i++)
    {
        Node* tempNode=this->neigborList[i].fNode;
        while(tempNode)
        {
            cout<<i<<"->"<<tempNode->toNode<<",value="<<tempNode->value<<",visited="<<tempNode->visited<<endl;
            tempNode=tempNode->next;
        }
    }
}

// 建图时的插入操作
void Graph::insertNode(edge e)
{
    Node* tempNode1,*tempNode2;
    if(this->neigborList[e.from].fNode==NULL)
    {
        tempNode1=new Node;
        tempNode1->next=NULL;
        tempNode1->value=e.value;
        tempNode1->toNode=e.to;
        tempNode1->visited=0;
        this->neigborList[e.from].fNode=tempNode1;
    }
    else
    {
        tempNode1=this->neigborList[e.from].fNode;
        while(tempNode1->next!=NULL)
        {
            tempNode1=tempNode1->next;
        }
        tempNode1->next=new Node;
        tempNode1=tempNode1->next;
        tempNode1->value=e.value;
        tempNode1->toNode=e.to;
        tempNode1->visited=0;
        tempNode1->next=NULL;
    }
    if(this->neigborList[e.to].fNode==NULL)
    {
        tempNode2=new Node;
        tempNode2->next=NULL;
        tempNode2->value=e.value;
        tempNode2->toNode=e.from;
        tempNode2->visited=0;
        this->neigborList[e.to].fNode=tempNode2;
    }
    else
    {
        tempNode2=this->neigborList[e.to].fNode;
        while(tempNode2->next!=NULL)
        {
            tempNode2=tempNode2->next;
        }
        tempNode2->next=new Node;
        tempNode2=tempNode2->next;
        tempNode2->value=e.value;
        tempNode2->toNode=e.from;
        tempNode2->visited=0;
        tempNode2->next=NULL;
    }
    this->neigborList[e.from].length++;
    this->neigborList[e.to].length++;
}

void Graph::createNode(edge e[],int length)
{
    for(int i=0;i<length;i++)
    {
        insertNode(e[i]);
    }
}

void Graph::clearVisited()
{
    Node* tempNode;
    for(int i=0;i<this->length;i++)
    {
        tempNode=this->neigborList[i].fNode;
        while(tempNode)
        {
            tempNode->visited=0;
            tempNode=tempNode->next;
        }
    }
}

void Graph::setVisited(Node* node,int i)
{   
    node->visited=1;
    Node* tempNode=this->neigborList[node->toNode].fNode;
    while(tempNode->toNode!=i)
    {
        tempNode=tempNode->next;
    }
    tempNode->visited=1;

}

void Graph::BFS(int begin)
{
    Node* tempNode;
    int tempIndex;
    queue<int> q;
    q.push(begin);
    int *visited=new int[this->length];
    for(int i=0;i<this->length;i++)
    {
        visited[i]=0;
    }
    visited[begin]=1;
    // this->setVisited();
    while(!q.empty())
    {
        tempIndex=q.front();
        cout<<tempIndex<<' ';
        q.pop();
        tempNode=this->neigborList[tempIndex].fNode;
        while(tempNode!=NULL)
        {
            if(visited[tempNode->toNode]==0)
            {
                q.push(tempNode->toNode);
                this->setVisited(tempNode,tempIndex);
                visited[tempNode->toNode]=1;
            }
            tempNode=tempNode->next;
        }
    }
    this->clearVisited();
}

void Graph::DFS(int begin,int visited[])
{
    visited[begin]=1;
    cout<<begin<<' ';
    Node* tempNode=this->neigborList[begin].fNode;
    while(tempNode!=NULL)
    {
        if(visited[tempNode->toNode]==0)
        {
            this->setVisited(tempNode,begin);
            DFS(tempNode->toNode,visited);
        }
        tempNode=tempNode->next;
    }
}

int main()
{
    edge e[6];
    e[0]={0,1,1};
    e[1]={0,2,1};
    e[2]={0,4,1};
    e[3]={2,3,1};
    e[4]={3,5,1};
    e[5]={4,5,1};
    Graph g(6);
    g.createNode(e,6);
    g.showGraph();
    g.BFS(0);
    cout<<endl;
    int *visited=new int[g.getLength()];
    for(int i=0;i<g.getLength();i++)
    {
        visited[i]=0;
    }
    g.DFS(0,visited);
}
